// https://www.lintcode.com/problem/previous-permutation/description

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    vector<int> previousPermuation(vector<int> &nums) {
        // int * array = new int[nums.size()];
        // memcpy(array, &nums[0], nums.size() * sizeof(int));
        // prev_permutation(nums.begin(), nums.end());
        // return nums;
        
        // 找到升序结束的地方，将比该数字小的最大的一个数和该数字对换，之后后面改为降序
        if (nums.size() <= 1) return nums;
        int i = nums.size() - 1;
        while (i > 0 && nums[i - 1] <= nums[i]) i--; //注意是<=
        if (i == 0) 
        {
            reverse(nums.begin(), nums.end());
            return nums;
        }
        i--;
        reverse(nums.begin() + i + 1, nums.end());
        int j = i + 1;
        while(nums[j] >= nums[i]) j++; //注意这里要>=
        if (j > i) swap(nums[i], nums[j]);
        return nums;
    }
};